/*
 * This code / file / algorithm is completely free to use and modify as necessary.
 * Any attribution is welcome and highly appriciated.
 */
package com.aaaa.scheduler.scheduler.nsga;


import com.aaaa.scheduler.pojo.Chromosome;
import com.aaaa.scheduler.scheduler.genetic.GeneticConfiguration;
import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.ToString;

import java.util.*;

/**
 * 
 * 
 * @author  Debabrata Acharya <debabrata.acharya@icloud.com>
 * @version 2.0
 * @since   2.0
 */
public class NSGAII {

    /**
     * 我支配你
     */
    private static final int DOMINANT = 1;
    /**
     * 你支配我
     */
    private static final int INFERIOR = 2;
    /**
     * 谁也不支配谁
     */
    private static final int NON_DOMINATED = 3;

    /**
     * 功能描述：快速非支配排序  计算拥挤度
     *
     */
    public static void fastNonDominatedSort(final Chromosome[] population) {

        NSGAII.fastNonDominated(population);
//        NSGAII.crowdingDistanceAssignment(population);

        //根据rank 对种群中所有染色体升序排序
        Arrays.sort(population,(o1, o2) -> {
            return o1.getRank() - o2.getRank();
        });

    }
    /**
     * 功能描述：从大种群中选择个体 计算部分染色体的拥挤度 选择rank小的非支配层的个体、拥挤度大的个体  并根据排序设置适应度
     *
     */
    public static Chromosome[] getChildAfterCrowdingDistanceAssignment(final Chromosome[] combinedPopulation) {
        //拿到处于种群大小边界的染色体排名  只对处于这个rank的非支配级进行排序
        int lastNonDominatedSetRank = combinedPopulation[GeneticConfiguration.POPULATION_SIZE-1].getRank();

        //对处于种群大小临界的非支配解集 以拥挤度进行降序排序
        //先找到这个rank的非支配集的范围，再调用Arrays.sort进行排序
        int rankStartIndex = -1, rankEndIndex = -1;
        for(int i = 0; i < combinedPopulation.length; i++){
            if((rankStartIndex < 0) && (combinedPopulation[i].getRank() == lastNonDominatedSetRank))
                rankStartIndex = i;
            if((rankStartIndex >= 0) && (combinedPopulation[i].getRank() == lastNonDominatedSetRank))
                rankEndIndex = i;
        }

        //DONE 拥挤度计算可以在这计算 只计算start和end之间的染色体的拥挤度
//        NSGAII.crowdingDistanceAssignmentPart(combinedPopulation, rankStartIndex, rankEndIndex);
//        Arrays.sort(combinedPopulation,rankStartIndex,rankEndIndex+1, (o1, o2) -> {
//            if(o1.getRank() == o2.getRank())
//                return Double.compare(o2.getCrowdingDistance(),o1.getCrowdingDistance());
//            return o1.getRank() - o2.getRank();
//        });

        //对所有个体进行拥挤度的计算   计算之后rank也要重新排序
        NSGAII.crowdingDistanceAssignment(combinedPopulation);
        Arrays.sort(combinedPopulation, (o1, o2) -> {
            if(o1.getRank() == o2.getRank())
                return Double.compare(o2.getCrowdingDistance(),o1.getCrowdingDistance());
            return o1.getRank() - o2.getRank();
        });

        Chromosome[] populace = new Chromosome[GeneticConfiguration.POPULATION_SIZE];
//        double zeng = 0.1 / (rankEndIndex - rankStartIndex + 1);
        for(int i = 0, j=1; i < GeneticConfiguration.POPULATION_SIZE; i++){
            populace[i] = combinedPopulation[i];
//            if(populace[i].getRank() == lastNonDominatedSetRank){//对于临界非支配层，染色体的适应度 在rank的基础上 加上一个增量 让拥挤度体现在适应度上
//                populace[i].setFitness(populace[i].getRank() + zeng * j);//拥挤度排名越靠后，fitness越大，越不好
//                j++;
//            }
        }
        
        return populace;
    }

    /**
     * 功能描述：快速非支配排序  计算rank
     *
     */
    private static void fastNonDominated(final Chromosome[] populace) {
        for(Chromosome chromosome : populace) chromosome.reset();
        Deque<Chromosome> queue = new LinkedList<>();
        
        for(int i = 0; i < populace.length - 1; i++) {
            for(int j = i + 1; j < populace.length; j++) {
                switch(NSGAII.dominates(populace[i], populace[j])) {
                    case NSGAII.DOMINANT:
                        populace[i].getDominatedChromosomeList().add(populace[j]);
                        populace[j].setDominationCount(populace[j].getDominationCount()+1);
                        break;

                    case NSGAII.INFERIOR:
                        populace[j].getDominatedChromosomeList().add(populace[i]);
                        populace[i].setDominationCount(populace[i].getDominationCount()+1);
                        break;

                    case NSGAII.NON_DOMINATED: break;
                }
            }
            if(populace[i].getDominationCount() == 0) {
                populace[i].setRank(1);//标注第一个非支配层
                queue.offer(populace[i]);
//                System.out.println(populace[i].getObjectiveFitnessValueList());
//                for (Chromosome chromosome : populace[i].getDominatedChromosomeList()) {
//                    System.out.print(chromosome.getObjectiveFitnessValueList() + " ");
//                }
//                System.out.println();
            }
        }
        if(populace[populace.length - 1].getDominationCount() == 0) {
            populace[populace.length - 1].setRank(1);//标注第一个非支配层
            queue.offer(populace[populace.length-1]);
        }

        while(!queue.isEmpty()){
            Chromosome c = queue.remove();
            for(Chromosome chromosome : c.getDominatedChromosomeList()) {
                chromosome.setDominationCount(chromosome.getDominationCount() - 1);
                if(chromosome.getDominationCount() == 0) {
                    chromosome.setRank(c.getRank() + 1);
                    queue.offer(chromosome);
                }
            }
        }

//        for(Chromosome c : populace){//染色体的适应度设置为rank排名
//            c.setFitness(c.getRank());
//        }

//        for(int i = 0; i < populace.length; i++) {//好像rank排名的逻辑不太对
//            for(Chromosome chromosome : populace[i].getDominatedChromosomeList()) {
//                chromosome.setDominationCount(populace[i].getDominationCount() - 1);
//                if(chromosome.getDominationCount() == 0) chromosome.setRank(populace[i].getRank() + 1);
//            }
//        }
    }

    /**
     * 功能描述：拥挤度计算 只计算种群中的一部分
     *
     */
    private static void crowdingDistanceAssignmentPart(final Chromosome[] nondominatedChromosomes, int start, int end) {
        for(int i = 0; i < GeneticConfiguration.objectiveList.size(); i++) {

            //根据第i个目标的值进行排序
            int finalI = i;
            Arrays.sort(nondominatedChromosomes, start, end+1,(o1, o2) -> {
                return Double.compare(o1.getObjectiveFitnessValueList().get(finalI),o2.getObjectiveFitnessValueList().get(finalI));
            });

            nondominatedChromosomes[start].setCrowdingDistance(Double.MAX_VALUE);
            nondominatedChromosomes[end].setCrowdingDistance(Double.MAX_VALUE);

            double maxObjectiveValue = nondominatedChromosomes[end].getObjectiveFitnessValueList().get(i);
            double minObjectiveValue = nondominatedChromosomes[start].getObjectiveFitnessValueList().get(i);

            for(int j = start+1; j < end; j++)
                if(nondominatedChromosomes[j].getCrowdingDistance() < Double.MAX_VALUE)
                    nondominatedChromosomes[j].setCrowdingDistance(nondominatedChromosomes[j].getCrowdingDistance()
                            + ((nondominatedChromosomes[j + 1].getObjectiveFitnessValueList().get(i)
                            - nondominatedChromosomes[j - 1].getObjectiveFitnessValueList().get(i)) / (maxObjectiveValue - minObjectiveValue)));

        }
    }


    /**
     * 功能描述：所有染色体进行拥挤度计算
     *
     */
    private static void crowdingDistanceAssignment(final Chromosome[] nondominatedChromosomes) {

        int size = nondominatedChromosomes.length;

        for(int i = 0; i < GeneticConfiguration.objectiveList.size(); i++) {

            //根据第i个目标的值进行排序
            int finalI = i;
            Arrays.sort(nondominatedChromosomes,(o1, o2) -> {
                return Double.compare(o1.getObjectiveFitnessValueList().get(finalI),o2.getObjectiveFitnessValueList().get(finalI));
            });

            nondominatedChromosomes[0].setCrowdingDistance(Double.MAX_VALUE);
            nondominatedChromosomes[size - 1].setCrowdingDistance(Double.MAX_VALUE);

            double maxObjectiveValue = nondominatedChromosomes[size - 1].getObjectiveFitnessValueList().get(i);
            double minObjectiveValue = nondominatedChromosomes[0].getObjectiveFitnessValueList().get(i);

            for(int j = 1; j < size - 1; j++)
                if(nondominatedChromosomes[j].getCrowdingDistance() < Double.MAX_VALUE)
                    nondominatedChromosomes[j].setCrowdingDistance(nondominatedChromosomes[j].getCrowdingDistance()
                            + ((nondominatedChromosomes[j + 1].getObjectiveFitnessValueList().get(i)
                            - nondominatedChromosomes[j - 1].getObjectiveFitnessValueList().get(i)) / (maxObjectiveValue - minObjectiveValue)));

        }
    }

    /**
     * 功能描述：判断谁支配谁
     *
     */
    private static int dominates(final Chromosome chromosome1, final Chromosome chromosome2) {

        if(NSGAII.isDominant(chromosome1, chromosome2)) return NSGAII.DOMINANT;
        else if(NSGAII.isDominant(chromosome2, chromosome1)) return NSGAII.INFERIOR;
        else return NSGAII.NON_DOMINATED;
    }

    /**
     * 功能描述：是否支配的判断逻辑
     *
     */
    private static boolean isDominant(final Chromosome chromosome1, final Chromosome chromosome2) {

        boolean isDominant = true;
        boolean atleastOneIsLarger = false;

        for(int i = 0; i < GeneticConfiguration.objectiveList.size(); i++) {

            if(chromosome1.getObjectiveFitnessValueList().get(i) > chromosome2.getObjectiveFitnessValueList().get(i)) {

                isDominant = false;
                break;
            } else if(!atleastOneIsLarger && (chromosome1.getObjectiveFitnessValueList().get(i) < chromosome2.getObjectiveFitnessValueList().get(i))){
                atleastOneIsLarger = true;
            }
        }

        return isDominant && atleastOneIsLarger;
    }


    public static void main(String[] args) {
        @Data
        @AllArgsConstructor
        @ToString
        class clazz{
            int rank;
            Double dominate;
        }
        clazz[] objects = new clazz[5];
        objects[0] = new clazz(1,0.1);
        objects[1] = new clazz(1,0.2);
        objects[2] = new clazz(2,0.1);
        objects[3] = new clazz(2,0.2);
        objects[4] = new clazz(2,0.7);
        Arrays.sort(objects, (o1, o2) -> {
            if(o1.getRank() == o2.getRank())
                return Double.compare(o2.getDominate(),o1.getDominate());
            return o1.getRank() - o2.getRank();
        });
        for (clazz object : objects) {
            System.out.println(object);
        }
    }
}

